package com.example.spring5.datastruct.tree;

import com.sun.source.tree.Tree;

import java.util.*;

/**
 * @Author: Hu Rui
 * @Date: 2021/11/13 16:28
 */
public class BinaryTree {

    /**
     * 创建二叉树
     * @param inputList
     * @return
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        TreeNode node = null;
        if (inputList == null || inputList.size() == 0) {
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null) {
            node = new TreeNode(data);
            node.left = createBinaryTree(inputList);
            node.right = createBinaryTree(inputList);
        }
        return node;
    }

    /**
     * 前序遍历
     * @param root
     * @param ans
     */
    public static void preOrderTraversal(TreeNode root,List<Integer> ans) {
        if (root == null) {
            return;
        }
        ans.add(root.data);
        preOrderTraversal(root.left,ans);
        preOrderTraversal(root.right,ans);
    }

    /**
     * 中序遍历
     * @param root
     * @param ans
     */
    public static void inOrderTraversal(TreeNode root,List<Integer> ans) {
        if (root == null) {
            return;
        }
        preOrderTraversal(root.left,ans);
        ans.add(root.data);
        preOrderTraversal(root.right,ans);
    }

    /**
     * 后序遍历
     * @param root
     * @param ans
     */
    public static void postOrderTraversal(TreeNode root,List<Integer> ans) {
        if (root == null) {
            return;
        }
        preOrderTraversal(root.left,ans);
        preOrderTraversal(root.right,ans);
        ans.add(root.data);
    }

    /**
     * 非递归的前序遍历
     * @param root 根节点
     * @param ans 前序遍历结果集合
     */
    public void preOrderTraversalWithStack(TreeNode root, List<Integer> ans) {
        var stack = new Stack<TreeNode>();
        var treeNode = root;
        while (treeNode != null || !stack.isEmpty()) {
            while (treeNode != null) {
                ans.add(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.left;
            }
            if (!stack.isEmpty()) {
                treeNode = stack.pop();
                treeNode = treeNode.right;
            }
        }
    }


    public static void main(String[] args) {
        LinkedList inputList = new LinkedList();
        for (int i = 0; i < 100; i++) {
            inputList.add(new Random().nextInt(1000));
        }
        TreeNode binaryTree = createBinaryTree(inputList);
        System.out.println(binaryTree.data);

        List<Integer> ans = new ArrayList<>();
//        preOrderTraversal(binaryTree,ans);
//        inOrderTraversal(binaryTree,ans);
        postOrderTraversal(binaryTree,ans);
        System.out.println(ans);
    }









    private static class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;

        public TreeNode(int data) {
            this.data = data;
        }
    }
}
